#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=10050;
const int INF=0x3f3f3f3f;
int map[MAXN][MAXN];
int lowcost[MAXN];
bool vis[MAXN];
int n,m;
int prim(){
	int pos=1;
	int Min=INF;
	int ans=0;
	memset(vis,false,sizeof(vis));
	//以1为初始点
	vis[pos]=true;
    printf("%d\n",pos);
    for(int i=1;i<=n;i++){
        printf("%d ",lowcost[i]);
    }
    printf("\n");
	//lowcost[i]表示pos到i的最小权值
	//pos这里不是一个特定点，是指当前最小生成树中的节点
	for(int i=1;i<=n;i++){
		if(i!=pos){
			lowcost[i]=map[pos][i];
		}
	}
    // for(int i=1;i<=n;i++){
    //     printf("%d ",lowcost[i]);
    // }
    // printf("\n");
    //注意这里是i<n 只剩下n-1条边
	for(int i=1;i<n;i++){
		Min=INF;
		//找出到当前生成树的所有节点的最小边权（即 lowcost ）位置
		for(int j=1;j<=n;j++){
			if(!vis[j] && lowcost[j]<Min){
				Min=lowcost[j];
                pos=j;
			}
		}
        printf("%d\n",Min);
		ans+=Min;
        printf("%d\n",ans);
		vis[pos]=true;
        //printf("%d\n",pos);
		//更新边权
        //更新边权的意思就是比如本来选定1点，而只有2 4点与之相连，因此lowcost里只有2 4有赋值
        //而通过上面选定一个lowcost最小的点4之后，与这个生成树相连的就要加上与4相连的节点
        //所以lowcost也就得更新，具体更新就是比较当前lowcost（初始为INF，所以每次都能往小的更新）与map[pos][j]的值
        //这里的pos与前面的pos是不同的，因此lowcost里面的值并不是确定的到哪一个点的最短路，而是到这整个生成树的最短路
		for(int j=1;j<=n;j++){
			if(!vis[j] && lowcost[j]>map[pos][j]){
				lowcost[j]=map[pos][j];
			}
		}
        // for(int i=1;i<=n;i++){
        //     printf("%d ",lowcost[i]);
        // }
        // printf("\n");
	}
    printf("%d\n",ans);
	return ans;
}
int main(void){
    n=7;
    memset(map,INF,sizeof(map));
    map[1][2]=map[2][1]=7;
    map[1][4]=map[4][1]=5;
    map[2][4]=map[4][2]=9;
    map[4][5]=map[5][4]=15;
    map[4][6]=map[6][4]=6;
    map[5][6]=map[6][5]=8;
    map[6][7]=map[7][6]=11;
    map[5][7]=map[7][5]=9;
    map[2][5]=map[5][2]=7;
    map[2][3]=map[3][2]=8;
    map[3][5]=map[5][3]=5;
    int ans=prim();
    printf("%d\n",ans);
	return 0;
}
